package hot100;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;

public class NumIslands {
    //节省时间，遍历后的‘1’全部改为'0'
    private int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int islandNum = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '0') {
                    islandNum++;
                    //不是海水也没有被访问过
                    bfs(grid, i, j);
                }
            }
        }

        return islandNum;
    }

    private void bfs(char[][] grid, int i, int j) {
        int m = grid.length;
        int n = grid[0].length;
        Deque<int[]> que = new ArrayDeque<>();
        que.addLast(new int[]{i, j});

        while (!que.isEmpty()) {
            int[] cur = que.removeFirst();
            int curY = cur[0];
            int curX = cur[1];
            grid[curY][curX] = '0';

            for (int k = 0; k < 4; k++) {
                int nextY = curY + dir[k][0];
                int nextX = curX + dir[k][1];

                if (nextY < 0 || nextY >= m) continue;
                if (nextX < 0 || nextX >= n) continue;

                if (grid[nextY][nextX] != '0') {
                    grid[nextY][nextX] = '0';
                    que.addLast(new int[]{nextY, nextX});
                }
            }
        }
    }

    @Test
    public void test() {
        char[][] grid = {
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}
        };

        System.out.println(numIslands(grid));
    }
}
